package com.atguigui.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 417.太平洋大西洋水流问题
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/4/27 8:40
 */
public class P417PacificAtlanticWaterFlow {
    public static void main(String[] args) {
        Solution solution = new P417PacificAtlanticWaterFlow().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //四个流向 往左，往右，往上，往下
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        //高度
        int[][] heights;
        int m, n;

        public List<List<Integer>> pacificAtlantic(int[][] heights) {

            this.heights = heights;
            //行
            this.m = heights.length;
            //列
            this.n = heights[0].length;

            //太平洋
            boolean[][] pacific = new boolean[m][n];
            //大西洋
            boolean[][] atlantic = new boolean[m][n];

            //四个方向入手
            for (int i = 0; i < m; i++) {
                bfs(i, 0, pacific);
            }
            for (int j = 1; j < n; j++) {
                bfs(0, j, pacific);
            }
            for (int i = 0; i < m; i++) {
                bfs(i, n - 1, atlantic);
            }
            for (int j = 0; j < n - 1; j++) {
                bfs(m - 1, j, atlantic);
            }

            List<List<Integer>> result = new ArrayList<List<Integer>>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (pacific[i][j] && atlantic[i][j]) {
                        List<Integer> cell = new ArrayList<Integer>();
                        cell.add(i);
                        cell.add(j);
                        result.add(cell);
                    }
                }
            }

            return result;
        }

        public void bfs(int row, int col, boolean[][] ocean) {
            //如果已经便利过则退出
            if (ocean[row][col]) {
                return;
            }
            ocean[row][col] = true;
            Queue<int[]> queue = new ArrayDeque<int[]>();
            //插入队列
            queue.offer(new int[]{row, col});

            //判断队列不为空
            while (!queue.isEmpty()) {
                //检索并删除该队列的头部，如果该队列为空则返回null
                //吐出一个岛屿坐标
                int[] cell = queue.poll();
                for (int[] dir : dirs) {
                    //更新每个岛屿坐标四周新的位置信息
                    int newRow = cell[0] + dir[0], newCol = cell[1] + dir[1];
                    //比较是否已经到达两个洋的周边，比较是否是 >= 自己，判断是否已经遍历过
                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[cell[0]][cell[1]] && !ocean[newRow][newCol]) {
                        //标识已经便利过
                        ocean[newRow][newCol] = true;
                        //插入队列
                        queue.offer(new int[]{newRow, newCol});
                    }
                }
            }


        }

    }
}
